public class Sort {
    // 归并排序---递归
    public static void mergeSort(int[] array) {
        //先将数组拆分
        mergeSortChild(array,0,array.length-1);
    }
    //拆分数组
    public  static  void mergeSortChild(int [] array,int start,int end){
        if(start==end){
            return;
        }
        int mid=(start+end)/2;
        mergeSortChild(array,start,mid);
        mergeSortChild(array,mid+1,end);
        //合并
        merge(array,start,mid,end);
    }
    //将两个数组进行合并
    public static void merge(int[] arraty,int start,int mid,int end){
        int s1=start;
        int e1=mid;
        int s2=mid+1;
        int e2=end;
        int []arr=new int[end-start+1];
        int count=0;
        while(s1<=e1&&s2<=e2){
            if(arraty[s1]<=arraty[s2]){
                arr[count++]=arraty[s1++];
            }else{
                arr[count++]=arraty[s2++];
            }
        }
      while(s1<=e1){
          arr[count++]=arraty[s1++];
      }
      while(s2<=e2){
          arr[count++]=arraty[s2++];
      }
      //将arr数组start到end之间有序的数值拷贝array中
        for (int i = 0; i <count; i++) {
            arraty[i+start]=arr[i];
        }

    }

// 归并排序---非递归
    public static void mergeSort1(int[] array) {
        int gap=1;
        while(gap<array.length){
            for (int i = 0; i <array.length ; i=i+2*gap) {
                int left=i;
                int mid=left+gap-1;
                int right=mid+gap;
                if(mid>=array.length){
                    mid=array.length-1;
                }
                if(right>=array.length){
                    right=array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap=gap*2;
        }
    }

// 计数排序
    public static void countSort(int[] array) {
       //找数组中的最大值和最小值
        int min=array[0];
        int max=array[0];
        for (int i = 0; i <array.length ; i++) {
            if(array[i]<min){
                min=array[i];
            }
            if(array[i]>max){
                max=array[i];
            }
        }
        //开辟一个数组
        int len=max-min+1;
        int [] tmp=new int[len];
        for (int i = 0; i <array.length ; i++) {
            int val=array[i];
            tmp[val-min]++;
        }
        int index=0;
        for(int i=0;i< tmp.length;i++){
            while(tmp[i]>0){
                array[index]=i+min;
                tmp[i]--;
                index++;
            }
        }
    }
}
